package com.chenken.graph;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class ListGraph<V,E> extends Graph<V,E>{
	
	/**
	 * 一个V对应一个Vertex
	 * 对外界是V，内部是Vertex对象
	 */
	private Map<V, Vertex<V, E>> vertices = new HashMap<V, Vertex<V, E>>();
	
	/**
	 * 所有的边
	 */
	private Set<Edge<V, E>> edges = new HashSet<Edge<V, E>>();
	
	/**
	 * 权重比较器
	 */
	private Comparator<Edge<V, E>> weightComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
			return weightManager.compare(e1.weight, e2.weight);
	};
	
	public ListGraph() {}
	
	public ListGraph(WeightManager<E> weightManager) {
		super(weightManager);
	}

	public void print() {
		vertices.forEach((V v,Vertex<V, E> vertex) -> {
			System.out.println(v);
			System.out.println("-----------OUT-------------");
			System.out.println(vertex.outEdges);
			System.out.println("-----------IN-------------");
			System.out.println(vertex.inEdges);
		});
		System.out.println("------------------------edges--------------------------");
		edges.forEach((Edge<V, E> edge) -> {
			System.out.println(edge);
		});
	}

	@Override
	public int edgesSize() {
		return edges.size();
	}

	@Override
	public int verticesSize() {
		return vertices.size();
	}

	@Override
	public void addVertex(V v) {
		if(vertices.containsKey(v)) return;
		vertices.put(v, new Vertex<>(v));
	}

	@Override
	public void addEdge(V from, V to) {
		addEdge(from, to, null);
	}

	@Override
	public void addEdge(V from, V to, E weight) {
		//	获取 from顶点
		Vertex<V, E> fromVertex = vertices.get(from);
		if(fromVertex == null) {
			fromVertex = new Vertex<V, E>(from);
			vertices.put(from, fromVertex);
		}
		//	获取 to顶点
		Vertex<V, E> toVertex = vertices.get(to);
		if(toVertex == null) {
			toVertex = new Vertex<V, E>(to);
			vertices.put(to, toVertex);
		}
		//make an edge
		Edge<V, E> edge = new Edge<V, E>(fromVertex,toVertex);
		edge.weight = weight;
		
		//delete old edge
		if(fromVertex.outEdges.remove(edge)) {
			toVertex.inEdges.remove(edge);
			edges.remove(edge);
		}
		
		fromVertex.outEdges.add(edge);
		toVertex.inEdges.add(edge);
		edges.add(edge);
	}

	@Override
	public void removeVertex(V v) {
		Vertex<V, E> vertex = vertices.get(v);
		if(vertex == null) return;
		for (Edge<V, E> edge:vertex.inEdges) {
			//from顶点中删除该edge
			edge.from.outEdges.remove(edge);
			//set中删除该edge
			edges.remove(edge);
		}
		for (Edge<V, E> edge:vertex.outEdges) {
			//	从to顶点的inEdges中删除该edge
			edge.to.inEdges.remove(edge);
			//	从set中删除该edge
			edges.remove(edge);
		}
		vertex.inEdges.clear();
		vertex.outEdges.clear();
		vertices.remove(v);
	}

	@Override
	public void removeEdge(V from, V to) {
		Vertex<V, E> fromVertex = vertices.get(from);
		Vertex<V, E> toVertex = vertices.get(to);
		if(fromVertex == null || toVertex == null) return;
		Edge<V,E> edge = new Edge<V,E>(fromVertex, toVertex);
		if(fromVertex.outEdges.remove(edge)) {
			toVertex.inEdges.remove(edge);
			edges.remove(edge);
		}
	}
	
	@Override
	public void bfs(V begin,VertexVisitor<V> visitor) {
		if(visitor == null) return;
		Vertex<V, E> beginVertex = vertices.get(begin);
		if(beginVertex == null) return;
		Set<Vertex<V, E>> visitedVertices = new HashSet<Vertex<V, E>>();
		//use queue
		Queue<Vertex<V, E>> queue = new LinkedList<Vertex<V,E>>();
		queue.offer(beginVertex);
		visitedVertices.add(beginVertex);
		
		while(!queue.isEmpty()) {
			Vertex<V, E> vertex = queue.poll();
			if(visitor.visit(vertex.value)) {
				return;
			}
			//make outEdges.to into queue
			for(Edge<V, E> edge:vertex.outEdges) {
				if(visitedVertices.contains(edge.to)) continue;
				queue.offer(edge.to);
				visitedVertices.add(edge.to);
			}
		}
	}
	
	/**
	 * 深度优先搜索-非递归
	 */
	@Override
	public void dfs(V begin,VertexVisitor<V> visitor) {
		if(visitor == null) return;
		
		Vertex<V, E> beginVertex = vertices.get(begin);
		if(beginVertex == null) return;
		Set<Vertex<V, E>> visitedVertices = new HashSet<Vertex<V, E>>();
		Stack<Vertex<V, E>> stack = new Stack<Vertex<V, E>>();
		
		stack.push(beginVertex);
		visitedVertices.add(beginVertex);
		if(visitor.visit(beginVertex.value)) {
			return;
		}
		
		while(!stack.isEmpty()) {
			Vertex<V, E> vertex = stack.pop();
			for(Edge<V, E> edge:vertex.outEdges) {
				if(visitedVertices.contains(edge.to)) continue;
				
				stack.push(edge.from);
				stack.push(edge.to);
				visitedVertices.add(edge.to);
				if(visitor.visit(edge.to.value)) {
					return;
				}
				break;
			}
		}
	}
	
	/**
	 * 深度优先搜索-递归
	 * @param begin
	 */
	public void dfs2(V begin) {
		Vertex<V, E> beginVertex = vertices.get(begin);
		if(beginVertex == null) return;
		dfs2(beginVertex,new HashSet<>());
	}
	
	public void dfs2(Vertex<V, E> vertex,Set<Vertex<V,E>> visitedVertices) {
		System.out.println(vertex.value);
		visitedVertices.add(vertex);
		for(Edge<V, E> edge:vertex.outEdges) {
			if(visitedVertices.contains(edge.to)) continue;
			dfs2(edge.to,visitedVertices);
		}
	}
	
	/**
	 * 顶点
	 * @param <V>
	 * @param <E>
	 */
	private static class Vertex<V,E>{
		
		V value;
		
		/**
		 * 入度
		 */
		Set<Edge<V, E>> inEdges = new HashSet<Edge<V, E>>();
		
		/**
		 * 出度
		 */
		Set<Edge<V, E>> outEdges = new HashSet<Edge<V, E>>();
		
		public Vertex(V value) {
			this.value = value;
		}
		
		/**
		 * 比较2个顶点是否相等
		 * value是否相等
		 */
		@Override
		public boolean equals(Object obj) {
			Vertex<V,E> vertex = (Vertex<V,E>)obj;
			return Objects.equals(value,vertex.value);
		}
		
		@Override
		public int hashCode() {
			return value == null ? 0 : value.hashCode();
		}

		@Override
		public String toString() {
			String valueString = value == null ? "null" : value.toString();
			return valueString;
		}
	}
	
	/**
	 * 边
	 * @param <V>
	 * @param <E>
	 */
	private static class Edge<V,E>{
		
		Vertex<V,E> from;
		
		Vertex<V,E> to;
		
		/**
		 * 权值
		 */
		E weight;
		
		public Edge(Vertex<V, E> from, Vertex<V, E> to) {
			this.from = from;
			this.to = to;
		}

		/**
		 * 比较2条边是否相等
		 * 边的from顶点和to顶点是否相等
		 */
		@Override
		public boolean equals(Object obj) {
			Edge<V,E> edge = (Edge<V,E>)obj;
			return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
		}
		
		@Override
		public int hashCode() {
			int fromHashCode = from.hashCode();
			int toHashCode = to.hashCode();
			return fromHashCode * 31 + toHashCode;
		}

		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}
		
		EdgeInfo<V, E> info(){
			return new EdgeInfo<V,E>(from.value,to.value,weight);
		}
	}

	@Override
	public Set<EdgeInfo<V, E>> mst() {
		return prim();
	}
	
	/**
	 * 最小生成树：prim算法
	 * @return
	 */
	private Set<EdgeInfo<V, E>> prim() {
		Iterator<Vertex<V, E>> iterator = vertices.values().iterator();
		if(!iterator.hasNext()) {
			return null;
		}
		Set<EdgeInfo<V, E>> edgeInfos = new HashSet<EdgeInfo<V, E>>();
		//	拿到起点
		Vertex<V, E> vertex = iterator.next();
		//	优先级队列:堆
		PriorityQueue<Edge<V, E>> heap = new PriorityQueue<Edge<V, E>>(weightComparator);
		heap.addAll(vertex.outEdges);
		Set<Vertex<V, E>> addedVertices = new HashSet<Vertex<V, E>>();
		int edgeSize = vertices.size()-1;
		//当边的数量达到了顶点数量-1
		while(!heap.isEmpty() && edgeInfos.size() < edgeSize) {
			//	拿到最小的边加到edgeInfos，并将其从堆顶删除
			Edge<V, E> edge = heap.remove();
			if(addedVertices.contains(edge.to)) continue;//已经加过了
			edgeInfos.add(edge.info());
			addedVertices.add(edge.to);
			heap.addAll(edge.to.outEdges);
		}
		return edgeInfos;
	}
	
	/**
	 * 最小生成树：kruskal算法
	 * @return
	 */
	private Set<EdgeInfo<V, E>> kruskal() {
		return null;
	}
}
